package lanqiaoDemo;

import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class Main {
    public static void main4(String[] args) {
        Scanner scan = new Scanner(System.in);
        //反向遍历
        for(int i = 10000000 ; i > 0 ; i--){
            if(check(i)){// i为目标则打印结果，并结束循环
                System.out.println(i);
                break;
            }
        }
        scan.close();
    }

    /**
     *检查该数是否为类斐波那契循环数
     */
    public static boolean check(int x){
        String s = x + "";
        // 获取位数
        int l = s.length();
        int[] dp = new int[l];
        // 数x的每一位都拆出来存入数组
        for(int i = 0 ; i < l ; i++){
            dp[i] = s.charAt(i) - '0';
        }
        int sum = 0 ;
        // 迭代数组检查该数是否为类斐波那契循环数
        for(int i = l ; sum < x ; i++){
            sum = Arrays.stream(dp).sum();// 数组求和
            dp[i%l] = sum;
        }
        // 跳出循环后sum >= x
        return sum == x;
    }

    //类斐波那契循环数
    public static void main3(String[] args) {
        int ret = 197;
        for (int i = 10000000; i>0; i--) {
            if(cheak(i)!=0){
                System.out.println(i);
                return ;
            }
        }
    }

    private static int cheak(int val){
        long tmp = val;
        int count = 0;
        List<Long> list = new ArrayList<>();
        while(tmp>0){
            list.add((tmp%10));
            tmp /= 10;
            count++;
        }
        int l = 0;
        int r = count-1;
        while(l<r){
            long tmp1 = list.get(l);
            list.set(l,list.get(r));
            list.set(r,tmp1);
            l++;
            r--;
        }
        while(list.get(list.size()-1)<=val){
            long sum = 0;
            for (int i = list.size()-1; i > list.size()-1-count; i--) {
                sum += list.get(i);
            }
            if(sum==val){
                return val;
            }else {
                list.add(sum);
            }
        }
        return 0;
    }

    //最大开支
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            int k = scanner.nextInt();
            int b = scanner.nextInt();
            //(k(j)+jb-kj-k-kb
            for (int j = 1; j <= n; j++) {
                int cost = 2*k*j+b-k;
                if(cost>0){
                    list.add(cost);
                }else {
                    break;
                }
            }
        }
        long maxCost = 0;
        int num = Math.min(n,list.size());
        list.sort((i,j)->{
            return j-i;
        });
        for (int i = 0; i < num; i++) {
            maxCost += list.get(i);
        }
        System.out.println(maxCost);
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int menoy = scanner.nextInt();
        int[] dp = new int[menoy+1];
        dp[0] = 0;
        for (int i = 1; i <= menoy; i++) {
            if(i<5){
                dp[i] = dp[i-1]+1;
            }else if(i>=5 && i<11){
                dp[i] = Math.min(dp[i-1],dp[i-5])+1;
            }else {
                dp[i] = Math.min(dp[i-1],Math.min(dp[i-5],dp[i-11]))+1;
            }
        }
        System.out.println(dp[menoy]);
    }
}
